package com.biancheng.biancheng.biancheng3;

public class 机器人行走问题 {

    public static void main(String[] args) {
        System.out.println("============动态规划===========");
        System.out.println("方法数为："+Cmain(5,3,3,4));
    }
    //根据暴力递归来改成动态规划
    public static int Cmain(int n,int k,int begin,int end) {
        if(n<1||k<0||begin<=0||begin>n|end<=0||end>n)
            return -1;
        int dp[][]=new int[n+1][k+1];
        for(int i=0;i<=n;i++) {
            for(int j=0;j<=k;j++)
                dp[i][j]=-1;
        }
        return MaxMethod1(n,k,begin,end,dp);
    }
    public static int MaxMethod1(int n,int k,int begin,int end,int dp[][]) {
        if(dp[begin][k]!=-1)
            return dp[begin][k];
        //之前没有算过
        int ans=0;
        if(k==0)
            ans=begin==end?1:0;
        else if(begin==1)
            ans=MaxMethod1(n,k-1,2,end,dp);
        else if(begin==n)
            ans=MaxMethod1(n,k-1,begin-1,end,dp);
        else
            ans=MaxMethod1(n,k-1,begin+1,end,dp)+MaxMethod1(n,k-1,begin-1,end,dp);
        dp[begin][k]=ans;
        return ans;
    }

}
